package stack;

/**
 * leet-code(42) 接雨水
 *
 * @author Ringo
 * @date 2022/2/5 11:36
 */
public class TrappingRainWater {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(height));
    }

    public static int trap(int[] height) {
        final int length = height.length;
        int[] stack = new int[length];
        int p = -1;
        int result = 0;
        for (int i = 0; i < length; ++i) {
            while (p > -1 && height[i] > height[stack[p]]) {
                int index = stack[p--];
                if (p == -1) break;
                int curWidth = i - stack[p] - 1;
                int curHeight = Math.min(height[i], height[stack[p]]) - height[index];
                result += curWidth * curHeight;
            }
            stack[++p] = i;
        }
        return result;
    }
}
